package org.taoge;

/**
 * 二分查找
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(binarySearch(arr, 20));
    }


    /**
     * 二分查找
     * @param arr 从小到大排序的数组
     * 问题探讨：
     *            1、关于是否需要在方法中校验arr是不是从小到大排序的数组，我的建议是：不需要
     * 方法本身的定位，就是要求传入一个有序的数组，至于原始数组的处理，需要在调用此方法前进行处理，实现解耦，不然方法的定位就没有边界
     * 同时也可以考虑增加一个方法，用于接受数组并进行排序。即使传入非排序数组，我们的方法也能处理，返回值是错误的
     *            2、关于是否需要对数组和target判空，我的建议是：需要
     *  因为不判断空或者非法值，会导致程序空指针或者其他异常。
     * @param target
     * @return
     */
    public static int binarySearch(int[] arr, int target){
        //参数及边界值校验
        if(arr==null || arr.length == 0 || target < arr[0] || target > arr[arr.length - 1]){
            return -1;
        }

        //我们首先将三个重要的变量初始化，left表示左边界，right表示右边界，mid表示中间值
        int left = 0; //while要判断，所以此处必须明确为0
        int right = arr.length - 1;  //while要判断，所以此处必须明确为  长度-1
        int mid;  //循环中每次动态获取，所以此处随便定义
        //循环遍历，找到target是否存在，不存在返回-1，存在返回下标
        while (left <= right){
            mid = left + (right - left) / 2;
            if(arr[mid] == target){
                return mid;
            } else if (arr[mid] > target) {  //如果中间值大于目标值，目标值在左侧找。则left不变，right变为mid-1
                right = mid - 1;
            }else{ //如果中间值大于目标值(等于的情况我们已经在开始处判断)，目标值在右侧找。则right不变，left变为mid+1
                left = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 如何记住这个算法呢？我们按照下面思路记忆即可
     * 前提条件
     *  1、数组是有序的
     *  2、方法的入参是arr和target
     *  3、返回值是下标，如果找不到，返回-1
     *
     *  关键参数
     *    1、left、right、mid的默认值判断。left和right定义在循环外，因为while要用，mid在循环中动态计算
     *    2、三个if语句的判断条件,都是基于arr[mid]。首先判断相等，然后判断大于和小于。
     *    3、arr[mid]>target，则说明目标值在左侧找，则right变为mid-1，left不变。
     *    4、arr[mid]<target，，则说明目标值在右侧找，则left变为mid+1，right不变。
     */

}
